#pragma once
// 带头单向不循环链表

template <class T>
struct chain_table_node
{
    T m_data;
    chain_table_node<T>* m_next;

    chain_table_node<T>(const T& data = T(), chain_table_node<T>* next = nullptr)
        : m_data(data)
        , m_next(next)
    {

    }
};

template <class T>
class chain_table
{
public:
    // 初始化, 一个只有头的chain table
    chain_table<T>()
        : m_head(new chain_table_node<T>)
        , m_size(0)
    {
        m_tail = m_head;
    }

    // push_back
    void push_back(const T& data)
    {
        chain_table_node<T>* new_node = new chain_table_node<T>(data);
        m_tail->m_next = new_node;
        m_tail = new_node;
        ++m_size;
    }

    // 删除 by data, 删除第一个m_data == data的节点
    void erase(const T& data)
    {
        chain_table_node<T>* cur = m_head->m_next;
        chain_table_node<T>* pre = m_head;

        while (cur != nullptr)
        {
            if (cur->m_data == data)
            {
                pre->m_next = cur->m_next;
                if (cur == m_tail)
                {
                    m_tail = pre;
                }
                delete cur;
                --m_size;
                return;
            }

            pre = cur;
            cur = cur->m_next;
        }
    }

    // find by data 返回第一个m_data == data的节点的地址, 没找到返回nullptr
    chain_table_node<T>* find(const T& data)
    {
        chain_table_node<T>* cur = m_head->m_next;
        while (cur != nullptr)
        {
            if (cur->m_data == data)
            {
                return cur;
            }
            cur = cur->m_next;
        }

        return nullptr;
    }

    // 升序插入, 每次插入的位置是第一个m_data > data节点位置的前一个位置
    void insert_ascending(const T& data);

    // 头节点
    chain_table_node<T>* gethead()
    {
        return m_head;
    }

private:
    chain_table_node<T>* m_head;
    chain_table_node<T>* m_tail;
    int m_size;
};

// 升序插入, 每次插入的位置是第一个m_data > data节点位置的前一个位置
template <class T>
void chain_table<T>::insert_ascending(const T& data)
{
    chain_table_node<T>* new_node = new chain_table_node<T>(data);

    chain_table_node<T>* cur = m_head->m_next;
    chain_table_node<T>* pre = m_head;

    while (cur != nullptr)
    {
        if (cur->m_data >= data)
        {
            pre->m_next = new_node;
            new_node->m_next = cur;
            ++m_size;
            return;
        }
        else 
        {
            pre = cur;
            cur = cur->m_next;
        }
    }

    // 没有比data大的节点 
    m_tail->m_next = new_node;
    m_tail = new_node;
    ++m_size;
}